//1926. 迷宫中离入口最近的出口

//给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。
//同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
//每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。
//你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
//请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 - 1 。

//class Solution {
//public:
//    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
//        int m = maze.size(), n = maze[0].size();
//        // 上下左右四个相邻坐标对应的行列变化量
//        int dirs[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };//使用static constexpr可以减少函数调用时的初始化次数
//        queue<tuple<int, int, int>> q;
//        // 入口加入队列并修改为墙
//        q.emplace(entrance[0], entrance[1], 0);
//        maze[entrance[0]][entrance[1]] = '+';
//        while (!q.empty()) {
//            auto [cx, cy, d] = q.front();
//            q.pop();
//            // 遍历四个方向相邻坐标
//            for (auto [dx, dy] : dirs) {
//                int nx = cx + dx;
//                int ny = cy + dy;
//                // 新坐标合法且不为墙
//                if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == '.') {
//                    if (nx == 0 || nx == m - 1 || ny == 0 || ny == n - 1) {
//                        // 新坐标为出口，返回距离作为答案
//                        return d + 1;
//                    }
//                    // 新坐标为空格子且不为出口，修改为墙并加入队列
//                    maze[nx][ny] = '+';
//                    q.emplace(nx, ny, d + 1);
//                }
//            }
//        }
//        // 不存在到出口的路径，返回 -1
//        return -1;
//    }
//};

//1091. 二进制矩阵中的最短路径

//给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 - 1 。
//二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
//路径途经的所有单元格的值都是 0 。
//路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
//畅通路径的长度 是该路径途经的单元格总数。

//class Solution {
//public:
//    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
//        int n = grid.size();
//        // 检查起点和终点是否为0
//        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
//            return -1;
//        }
//        // 建立八个方向的位移量//现代c++推荐写法int[][]与array<array<int,>,>都是扁平化的
//        constexpr array<array<int, 2>, 8> dirs =
//        { {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}} };
//        // 建立bfs队列
//        queue<pair<int, int>> q;
//        // 标记已访问的单元格子
//        vector<vector<bool>> visited(n, vector<bool>(n, false));
//        q.push({ 0, 0 });
//        int distance = 1;     // 起点入队，距离为1(起点)
//        visited[0][0] = true; // 表示当前起点坐标已经访问
//        while (!q.empty()) {
//            int size = q.size();
//            for (int i = 0; i < size; i++) {
//                auto [x, y] = q.front();
//                q.pop();
//                // 到达终点，返回当前距离
//                if (x == n - 1 && y == n - 1)
//                    return distance;
//                // 探索八个方向
//                for (auto [dx, dy] : dirs) {
//                    int nx = x + dx;
//                    int ny = y + dy;
//                    // 新坐标有效且为未访问且值为0
//                    if (nx >= 0 && nx < n && ny >= 0 && ny < n &&
//                        !visited[nx][ny] && grid[nx][ny] == 0) {
//                        visited[nx][ny] = true;
//                        q.push({ nx, ny }); // 当前坐标加入队列
//                    }
//                }
//            }
//            // 完成了一层，距离加1
//            distance++;
//        }
//        // 无法到达终点
//        return -1;
//    }
//};

//1162. 地图分析

//你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。
//请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 - 1。
//我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和(x1, y1) 这两个单元格之间的距离是 | x0 - x1 | +| y0 - y1 | 。

//class Solution {
//public:
//    static constexpr int dirs[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
//    static constexpr int MAX_N = 100 + 5;
//    static constexpr int INF = int(1E6);
//
//    int n;
//    int d[MAX_N][MAX_N];
//
//    struct Coordinate {
//        int x, y;
//    };
//
//    queue <Coordinate> q;
//
//    int maxDistance(vector<vector<int>>& grid) {
//        this->n = grid.size();
//        auto& a = grid;
//
//        for (int i = 0; i < n; ++i) {
//            for (int j = 0; j < n; ++j) {
//                d[i][j] = INF;
//            }
//        }
//
//        for (int i = 0; i < n; ++i) {
//            for (int j = 0; j < n; ++j) {
//                if (a[i][j]) {
//                    d[i][j] = 0;
//                    q.push({ i, j });
//                }
//            }
//        }
//
//        while (!q.empty()) {
//            auto f = q.front(); q.pop();
//            for (int i = 0; i < 4; ++i) {
//                int nx = f.x + dirs[i][0], ny = f.y + dirs[i][1];
//                if (!(nx >= 0 && nx <= n - 1 && ny >= 0 && ny <= n - 1)) continue;
//                if (d[nx][ny] > d[f.x][f.y] + 1) {
//                    d[nx][ny] = d[f.x][f.y] + 1;
//                    q.push({ nx, ny });
//                }
//            }
//        }
//
//        int ans = -1;
//        for (int i = 0; i < n; ++i) {
//            for (int j = 0; j < n; ++j) {
//                if (!a[i][j]) {
//                    ans = max(ans, d[i][j]);
//                }
//            }
//        }
//
//        return (ans == INF) ? -1 : ans;
//    }
//};

//542. 01 矩阵

//给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
//两个相邻元素间的距离为 1 。

//class Solution {
//    static constexpr array<array<int, 2>, 4> dirs = { {{-1, 0}, {1, 0}, {0, -1}, {0, 1}} };
//public:
//    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
//        int m = matrix.size(), n = matrix[0].size();
//        vector<vector<int>> dist(m, vector<int>(n));
//        vector<int8_t> seen(m * n);
//        queue<pair<int, int>> q;
//        // 将所有的 0 添加进初始队列中
//        for (int i = 0; i < m; ++i) {
//            for (int j = 0; j < n; ++j) {
//                if (matrix[i][j] == 0) {
//                    q.emplace(i, j);
//                    seen[i * n + j] = 1;
//                }
//            }
//        }
//
//        // 广度优先搜索
//        while (!q.empty()) {
//            auto [i, j] = q.front();
//            q.pop();
//            for (auto [di, dj] : dirs) {
//                int ni = i + di;
//                int nj = j + dj;
//                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni * n + nj]) {
//                    dist[ni][nj] = dist[i][j] + 1;
//                    q.emplace(ni, nj);
//                    seen[ni * n + nj] = 1;
//                }
//            }
//        }
//
//        return dist;
//    }
//};

//994. 腐烂的橘子

//在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
//值 0 代表空单元格；
//值 1 代表新鲜橘子；
//值 2 代表腐烂的橘子。
//每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
//返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 - 1 。

//class Solution {
//    static constexpr array<array<int, 2>, 4>dirs = { {{-1, 0}, {1, 0}, {0, -1}, {0, 1}} };
//public:
//    int orangesRotting(vector<vector<int>>& grid) {
//        int m = grid.size(), n = grid[0].size();
//        int fresh = 0;
//        vector<pair<int, int>> q;
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (grid[i][j] == 1) {
//                    fresh++; // 统计新鲜橘子个数
//                }
//                else if (grid[i][j] == 2) {
//                    q.emplace_back(i, j); // 一开始就腐烂的橘子
//                }
//            }
//        }
//
//        int ans = 0;
//        while (fresh && !q.empty()) {
//            ans++; // 经过一分钟
//            vector<pair<int, int>> nxt;
//            for (auto& [x, y] : q) { // 已经腐烂的橘子
//                for (auto [dx, dy] : dirs) { // 四方向
//                    int i = x + dx, j = y + dy;
//                    if (0 <= i && i < m && 0 <= j && j < n && grid[i][j] == 1) { // 新鲜橘子
//                        fresh--;
//                        grid[i][j] = 2; // 变成腐烂橘子
//                        nxt.emplace_back(i, j);
//                    }
//                }
//            }
//            q = move(nxt);
//        }
//
//        return fresh ? -1 : ans;
//    }
//};

//1765. 地图中的最高点

//给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由 陆地 和 水域 单元格组成的地图。
//如果 isWater[i][j] == 0 ，格子(i, j) 是一个 陆地 格子。
//如果 isWater[i][j] == 1 ，格子(i, j) 是一个 水域 格子。
//你需要按照如下规则给每个单元格安排高度：
//每个格子的高度都必须是非负的。
//如果一个格子是 水域 ，那么它的高度必须为 0 。
//任意相邻的格子高度差 至多 为 1 。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）
//找到一种安排高度的方案，使得矩阵中的最高高度值 最大 。
//请你返回一个大小为 m x n 的整数矩阵 height ，其中 height[i][j] 是格子(i, j) 的高度。如果有多种解法，请返回 任意一个 。

//class Solution {
//    static constexpr array<array<int, 2>, 4> dirs = { {{-1, 0}, {1, 0}, {0, -1}, {0, 1}} };
//public:
//    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
//        int m = isWater.size(), n = isWater[0].size();
//        vector<vector<int>> ans(m, vector<int>(n, -1)); // -1 表示该格子尚未被访问过
//        queue<pair<int, int>> q;
//        for (int i = 0; i < m; ++i) {
//            for (int j = 0; j < n; ++j) {
//                if (isWater[i][j]) {
//                    ans[i][j] = 0;
//                    q.emplace(i, j); // 将所有水域入队
//                }
//            }
//        }
//        while (!q.empty()) {
//            auto [qx, qy] = q.front();
//            for (auto [dx, dy] : dirs) {
//                int x = qx + dx, y = qy + dy;
//                if (0 <= x && x < m && 0 <= y && y < n && ans[x][y] == -1) {
//                    ans[x][y] = ans[qx][qy] + 1;
//                    q.emplace(x, y);
//                }
//            }
//            q.pop();
//        }
//        return ans;
//    }
//};

//934. 最短的桥

//给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
//岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。
//你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
//返回必须翻转的 0 的最小数目。

//class Solution {
//    static constexpr array<array<int, 2>, 4> dirs = { {{-1, 0}, {1, 0}, {0, -1}, {0, 1}} };
//public:
//    int shortestBridge(vector<vector<int>>& grid) {
//        int n = grid.size();
//        vector<pair<int, int>> island;
//        queue<pair<int, int>> qu;
//
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                if (grid[i][j] == 1) {
//                    qu.emplace(i, j);
//                    grid[i][j] = -1;
//                    while (!qu.empty()) {
//                        auto [x, y] = qu.front();
//                        qu.pop();
//                        island.emplace_back(x, y);
//                        for (auto [dx, dy] : dirs) {
//                            int nx = x + dx;
//                            int ny = y + dy;
//                            if (nx >= 0 && ny >= 0 && nx < n && ny < n && grid[nx][ny] == 1) {
//                                qu.emplace(nx, ny);
//                                grid[nx][ny] = -1;
//                            }
//                        }
//                    }
//                    for (auto&& [x, y] : island) {
//                        qu.emplace(x, y);
//                    }
//                    int step = 0;
//                    while (!qu.empty()) {
//                        int sz = qu.size();
//                        for (int i = 0; i < sz; i++) {
//                            auto [x, y] = qu.front();
//                            qu.pop();
//                            for (auto [dx, dy] : dirs) {
//                                int nx = x + dx;
//                                int ny = y + dy;
//                                if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
//                                    if (grid[nx][ny] == 0) {
//                                        qu.emplace(nx, ny);
//                                        grid[nx][ny] = -1;
//                                    }
//                                    else if (grid[nx][ny] == 1) {
//                                        return step;
//                                    }
//                                }
//                            }
//                        }
//                        step++;
//                    }
//                }
//            }
//        }
//        return 0;
//    }
//};

//2146. 价格范围内最高排名的 K 样物品

//给你一个下标从 0 开始的二维整数数组 grid ，它的大小为 m x n ，表示一个商店中物品的分布图。数组中的整数含义为：
//0 表示无法穿越的一堵墙。
//1 表示可以自由通过的一个空格子。
//所有其他正整数表示该格子内的一样物品的价格。你可以自由经过这些格子。
//从一个格子走到上下左右相邻格子花费 1 步。
//同时给你一个整数数组 pricing 和 start ，其中 pricing = [low, high] 且 start = [row, col] ，表示你开始位置为(row, col) ，
//同时你只对物品价格在 闭区间[low, high] 之内的物品感兴趣。同时给你一个整数 k 。
//你想知道给定范围 内 且 排名最高 的 k 件物品的 位置 。排名按照优先级从高到低的以下规则制定：
//距离：定义为从 start 到一件物品的最短路径需要的步数（较近 距离的排名更高）。
//价格：较低 价格的物品有更高优先级，但只考虑在给定范围之内的价格。
//行坐标：较小 行坐标的有更高优先级。
//列坐标：较小 列坐标的有更高优先级。
//请你返回给定价格内排名最高的 k 件物品的坐标，将它们按照排名排序后返回。如果给定价格内少于 k 件物品，那么请将它们的坐标 全部 返回。

//class Solution {
//    static constexpr array<array<int, 2>, 4> dirs = { {{-1, 0}, {1, 0}, {0, -1}, {0, 1}} };
//public:
//    vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int k) {
//        vector<vector<int>> ans;
//        int m = grid.size(), n = grid[0].size();
//        int low = pricing[0], high = pricing[1];
//        int sx = start[0], sy = start[1];
//        //bool vis[m][n]; memset(vis, 0, sizeof(vis));GCC/Clang编译器的极端性能优化条件下
//        vector<int8_t> vis(m * n);
//        vis[sx * n + sy] = true;
//        vector<pair<int, int>> q = { {sx, sy} };
//        while (!q.empty()) { // 分层 BFS
//            // 此时 q 内所有元素到起点的距离均相同，因此按照题目中的第 2~4 关键字排序后，就可以将价格在 [low,high] 内的位置加入答案
//            sort(q.begin(), q.end(), [&](auto& a, auto& b) {
//                int pa = grid[a.first][a.second], pb = grid[b.first][b.second];
//                return pa < pb || pa == pb && a < b;
//                });
//            for (const auto& [qf, qs] : q) {
//                int g = grid[qf][qs];
//                if (low <= g && g <= high) {
//                    ans.push_back({ qf, qs });
//                    if (ans.size() == k) return ans;
//                }
//            }
//            vector<pair<int, int>> qq;
//            for (const auto& [qx, qy] : q)
//                for (const auto& [dx, dy] : dirs) {
//                    int x = qx + dx, y = qy + dy;
//                    if (0 <= x && x < m && 0 <= y && y < n && !vis[x * n + y] && grid[x][y]) {
//                        vis[x * n + y] = true;
//                        qq.emplace_back(x, y);
//                    }
//                }
//            q = move(qq);
//        }
//        return ans;
//    }
//};

//1293. 网格中的最短路径

//给你一个 m* n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。
//如果您 最多 可以消除 k 个障碍物，请找出从左上角(0, 0) 到右下角(m - 1, n - 1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 - 1 。

//struct Nagato {
//    int x, y;
//    int rest;
//    Nagato(int _x, int _y, int _r) : x(_x), y(_y), rest(_r) {}
//};
//
//class Solution {
//    static constexpr array<array<int, 2>, 4> dirs = { {{-1, 0}, {1, 0}, {0, -1}, {0, 1}} };
//public:
//    int shortestPath(vector<vector<int>>& grid, int k) {
//        int m = grid.size(), n = grid[0].size();
//        if (m == 1 && n == 1) {
//            return 0;
//        }
//
//        k = min(k, m + n - 3);
//        int totalStates = m * n * (k + 1);
//        vector<int8_t> visited(totalStates, false);
//        queue<Nagato> q;
//        q.emplace(0, 0, k);
//        visited[0 * (n * (k + 1)) + 0 * (k + 1) + k] = true;
//
//        for (int step = 1; q.size() > 0; ++step) {
//            int cnt = q.size();
//            for (int _ = 0; _ < cnt; ++_) {
//                auto [x, y, rest] = q.front();//pop()后不能用引用
//                q.pop();
//                for (const auto& [dx, dy] : dirs) {
//                    int nx = x + dx, ny = y + dy;
//                    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
//                        int idx = nx * (n * (k + 1)) + ny * (k + 1) + rest;
//                        if (grid[nx][ny] == 0 && !visited[idx]) {
//                            if (nx == m - 1 && ny == n - 1) {
//                                return step;
//                            }
//                            q.emplace(nx, ny, rest);
//                            visited[idx] = true;
//                        }
//                        else if (grid[nx][ny] == 1 && rest > 0) {
//                            int new_rest = rest - 1;
//                            int new_idx = nx * (n * (k + 1)) + ny * (k + 1) + new_rest;
//                            if (!visited[new_idx]) {
//                                q.emplace(nx, ny, new_rest);
//                                visited[new_idx] = true;
//                            }
//                        }
//                    }
//                }
//            }
//        }
//        return -1;
//    }
//};

//909. 蛇梯棋

//给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n2 编号，编号遵循 转行交替方式 ，从左下角开始 （即，从 board[n - 1][0] 开始）的每一行改变方向。
//你一开始位于棋盘上的方格  1。每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进：
//选定目标方格 next ，目标方格的编号在范围[curr + 1, min(curr + 6, n2)] 。
//该选择模拟了掷 六面体骰子 的情景，无论棋盘大小如何，玩家最多只能有 6 个目的地。
//传送玩家：如果目标方格 next 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 next 。
//当玩家到达编号 n2 的方格时，游戏结束。
//如果 board[r][c] != -1 ，位于 r 行 c 列的棋盘格中可能存在 “蛇” 或 “梯子”。那个蛇或梯子的目的地将会是 board[r][c]。编号为 1 和 n2 的方格不是任何蛇或梯子的起点。
//注意，玩家在每次掷骰的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，玩家也 不能 继续移动。
//举个例子，假设棋盘是 [[-1, 4], [-1, 3]] ，第一次移动，玩家的目标方格是 2 。那么这个玩家将会顺着梯子到达方格 3 ，但 不能 顺着方格 3 上的梯子前往方格 4 。（简单来说，类似飞行棋，玩家掷出骰子点数后移动对应格数，遇到单向的路径（即梯子或蛇）可以直接跳到路径的终点，但如果多个路径首尾相连，也不能连续跳多个路径）
//返回达到编号为 n2 的方格所需的最少掷骰次数，如果不可能，则返回 - 1。

//class Solution {
//public:
//    int snakesAndLadders(vector<vector<int>>& board) {
//        int n = board.size();
//        vector<int8_t> vis(n * n + 1);
//        vis[1] = true;
//        queue<int> q;
//        q.push(1);
//        for (int step = 0; !q.empty(); step++) {
//            int qn = q.size();
//            for (int _ = 0; _ < qn; _++) {
//                int x = q.front();
//                q.pop();
//                if (x == n * n) { // 终点
//                    return step;
//                }
//                for (int y = x + 1; y <= min(x + 6, n * n); y++) {
//                    int r = (y - 1) / n, c = (y - 1) % n;
//                    if (r % 2) {
//                        c = n - 1 - c; // 奇数行从右到左
//                    }
//                    int nxt = board[n - 1 - r][c];
//                    if (nxt < 0) {
//                        nxt = y;
//                    }
//                    if (!vis[nxt]) {
//                        vis[nxt] = true; // 有环的情况下，避免死循环
//                        q.push(nxt);
//                    }
//                }
//            }
//        }
//        return -1; // 无法到达终点
//    }
//};

//1210. 穿过迷宫的最少移动次数

//你还记得那条风靡全球的贪吃蛇吗？
//我们在一个 n* n 的网格上构建了新的迷宫地图，蛇的长度为 2，也就是说它会占去两个单元格。蛇会从左上角（(0, 0) 和(0, 1)）开始移动。我们用 0 表示空单元格，用 1 表示障碍物。
//蛇需要移动到迷宫的右下角（(n - 1, n - 2) 和(n - 1, n - 1)）。
//每次移动，蛇可以这样走：
//如果没有障碍，则向右移动一个单元格。并仍然保持身体的水平／竖直状态。
//如果没有障碍，则向下移动一个单元格。并仍然保持身体的水平／竖直状态。
//如果它处于水平状态并且其下面的两个单元都是空的，就顺时针旋转 90 度。蛇从（(r, c)、(r, c + 1)）移动到 （(r, c)、(r + 1, c)）。
//如果它处于竖直状态并且其右面的两个单元都是空的，就逆时针旋转 90 度。蛇从（(r, c)、(r + 1, c)）移动到（(r, c)、(r, c + 1)）。
//返回蛇抵达目的地所需的最少移动次数。
//如果无法到达目的地，请返回 - 1。

//class Solution {
//    static constexpr array<array<int, 3>, 3> dirs = { {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}} };
//public:
//    int minimumMoves(vector<vector<int>>& grid) {
//        int n = grid.size(), qn{};
//        vector<int8_t> vis(n * n * 2);
//        vis[0] = true;
//        queue<tuple<int, int, int>> q;
//        q.emplace(0, 0, 0);
//        for (int step = 1; !q.empty(); step++) {
//            qn = q.size();
//            while (qn) {
//                qn--;
//                const auto [X, Y, S] = q.front();
//                q.pop();
//                for (const auto& [dx, dy, ds] : dirs) {
//                    int x = X + dx, y = Y + dy, s = S ^ ds;
//                    int x2 = x + s, y2 = y + (s ^ 1);
//                    if (x2 < n && y2 < n && !vis[x * n * 2 + y * 2 + s] &&
//                        grid[x][y] == 0 && grid[x2][y2] == 0 && (ds == 0 || grid[x + 1][y + 1] == 0)) {
//                        if (x == n - 1 && y == n - 2) return step;
//                        vis[x * n * 2 + y * 2 + s] = true;
//                        q.emplace(x, y, s);
//                    }
//                }
//            }
//        }
//        return -1;
//    }
//};

//675. 为高尔夫比赛砍树

//你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：
//0 表示障碍，无法触碰
//1 表示地面，可以行走
//比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
//每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
//你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
//你将从(0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 - 1 。
//可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

//class Solution {
//public:
//    static constexpr array<array<int, 2>, 4> dirs = { {{-1, 0}, {1, 0}, {0, -1}, {0, 1}} };
//    int bfs(vector<vector<int>>& forest, int sx, int sy, int tx, int ty) {
//        if (sx == tx && sy == ty) {
//            return 0;
//        }
//
//        int row = forest.size();
//        int col = forest[0].size();
//        int step = 0;
//        queue<pair<int, int>> qu;
//        vector<int8_t> vis(row * col);
//        qu.emplace(sx, sy);
//        vis[sx * col + sy] = true;
//        while (!qu.empty()) {
//            step++;
//            int sz = qu.size();
//            for (int _{}; _ < sz; _++) {
//                auto [cx, cy] = qu.front();
//                qu.pop();
//                for (auto& [dx, dy] : dirs) {
//                    int nx = cx + dx;
//                    int ny = cy + dy;
//                    if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
//                        if (!vis[nx * col + ny] && forest[nx][ny] > 0) {
//                            if (nx == tx && ny == ty) {
//                                return step;
//                            }
//                            qu.emplace(nx, ny);
//                            vis[nx * col + ny] = true;
//                        }
//                    }
//                }
//            }
//        }
//        return -1;
//    }
//
//    int cutOffTree(vector<vector<int>>& forest) {
//        vector<pair<int, int>> trees;
//        int row = forest.size();
//        int col = forest[0].size();
//        for (int i = 0; i < row; ++i) {
//            for (int j = 0; j < col; ++j) {
//                if (forest[i][j] > 1) {
//                    trees.emplace_back(i, j);
//                }
//            }
//        }
//        sort(trees.begin(), trees.end(), [&](const pair<int, int>& a, const pair<int, int>& b) {
//            return forest[a.first][a.second] < forest[b.first][b.second];
//            });
//
//        int cx = 0;
//        int cy = 0;
//        int ans = 0;
//        for (auto& [tf, ts] : trees) {
//            int steps = bfs(forest, cx, cy, tf, ts);
//            if (steps == -1) {
//                return -1;
//            }
//            ans += steps;
//            cx = tf;
//            cy = ts;
//        }
//        return ans;
//    }
//};

//749. 隔离病毒

//病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。
//假设世界由 m x n 的二维矩阵 isInfected 组成， isInfected[i][j] == 0 表示该区域未感染病毒，而  isInfected[i][j] == 1 表示该区域已感染病毒。可以在任意 2 个相邻单元之间的共享边界上安装一个防火墙（并且只有一个防火墙）。
//每天晚上，病毒会从被感染区域向相邻未感染区域扩散，除非被防火墙隔离。现由于资源有限，每天你只能安装一系列防火墙来隔离其中一个被病毒感染的区域（一个区域或连续的一片区域），且该感染区域对未感染区域的威胁最大且 保证唯一 。
//你需要努力使得最后有部分区域不被病毒感染，如果可以成功，那么返回需要使用的防火墙个数; 如果无法实现，则返回在世界被病毒全部感染时已安装的防火墙个数。

//// //Lambda 表达式//c++17
//// auto pair_hash = [](const std::pair<int, int>& p) {
////     return std::hash<int>()(p.first) ^ (std::hash<int>()(p.second) << 1);
//// };
//// auto pair_equal = [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
////     return a.first == b.first && a.second == b.second;
//// };
//// //需要指定初始桶数量和哈希/相等函数对象
//// std::unordered_set<std::pair<int, int>, decltype(pair_hash), decltype(pair_equal)> 
////     mySet(10, pair_hash, pair_equal);
//
//// //直接特化pair
//// namespace std {
////     template<>
////     struct hash<std::pair<int, int>> {
////         size_t operator()(const std::pair<int, int>& p) const {
////             return hash<int>()(p.first) ^ (hash<int>()(p.second) << 1);
////         }
////     };
//// }
//// std::unordered_set<std::pair<int, int>> mySet; 
//
//class Solution {
//    static constexpr array<array<int, 2>, 4> dirs = { {{-1, 0}, {1, 0}, {0, -1}, {0, 1}} };
//    struct PairHash {
//        size_t operator()(const std::pair<int, int>& p) const {
//            size_t h1 = std::hash<int>{}(p.first);
//            size_t h2 = std::hash<int>{}(p.second);
//            return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
//        }
//    };
//
//    struct PairEqual {
//        bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) const {
//            return a.first == b.first && a.second == b.second;
//        }
//    };
//
//public:
//    int containVirus(vector<vector<int>>& isInfected) {
//        int m = isInfected.size(), n = isInfected[0].size();
//        int ans = 0;
//
//        while (true) {//每次找出威胁最大的
//            // 使用透明哈希的unordered_set,但c++标准库没有标准的pair//c++20
//            vector<unordered_set<pair<int, int>, PairHash, PairEqual>> neighbors;
//            vector<int> firewalls;
//
//            for (int i = 0; i < m; ++i) {
//                for (int j = 0; j < n; ++j) {
//                    if (isInfected[i][j] == 1) {
//                        queue<pair<int, int>> q;
//                        unordered_set<pair<int, int>, PairHash, PairEqual> neighbor;
//                        int firewall = 0, idx = neighbors.size() + 1;
//                        q.emplace(i, j);
//                        isInfected[i][j] = -idx;
//
//                        while (!q.empty()) {
//                            auto [x, y] = q.front();
//                            q.pop();
//                            for (int d = 0; d < 4; ++d) {
//                                int nx = x + dirs[d][0];
//                                int ny = y + dirs[d][1];
//                                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
//                                    if (isInfected[nx][ny] == 1) {
//                                        q.emplace(nx, ny);
//                                        isInfected[nx][ny] = -idx;
//                                    }
//                                    else if (isInfected[nx][ny] == 0) {
//                                        ++firewall;
//                                        neighbor.emplace(nx, ny);
//                                    }
//                                }
//                            }
//                        }
//                        neighbors.push_back(move(neighbor));
//                        firewalls.push_back(firewall);
//                    }
//                }
//            }
//
//            if (neighbors.empty()) {
//                break;
//            }
//
//            int idx = max_element(neighbors.begin(), neighbors.end(), [](const auto& v0, const auto& v1) {
//                return v0.size() < v1.size(); }) - neighbors.begin();
//                ans += firewalls[idx];
//
//                for (int i = 0; i < m; ++i) {
//                    for (int j = 0; j < n; ++j) {
//                        if (isInfected[i][j] < 0) {
//                            if (isInfected[i][j] != -idx - 1) {
//                                isInfected[i][j] = 1;
//                            }
//                            else {
//                                isInfected[i][j] = 2;
//                            }
//                        }
//                    }
//                }
//
//                for (int i = 0; i < neighbors.size(); ++i) {
//                    if (i != idx) {
//                        for (const auto& [x, y] : neighbors[i]) {
//                            isInfected[x][y] = 1;
//                        }
//                    }
//                }
//
//                if (neighbors.size() == 1) {
//                    break;
//                }
//        }
//        return ans;
//    }
//};